package com.leetcode;

import java.util.Arrays;

public class Date250327 {
    public static void main(String[] args){
        //https://leetcode.cn/problems/valid-triangle-number/
        //有效三角形的个数
        int[] arr = new int[]{4,2,3,4};
        int ret = triangleNumber(arr);
        System.out.println(ret);

    }
    public static int triangleNumber(int[] nums) {
        //排序
        Arrays.sort(nums);
        int len = nums.length;
        int left = 0, right = len - 2, c = len - 1,ret = 0;
        while(c >= 2){
            if(nums[left] + nums[right] > nums[c]){
                ret += right - left;
                right--;
            }else{
                left++;
            }
            if(left == right){
                c--;
                left = 0;
                right = c-1;
            }
        }
        return ret;
    }
}
